package leetcode;

/**
 * 1143. 最长公共子序列    https://leetcode.cn/problems/longest-common-subsequence/
 */
public class LeetCode1143 {

    /**
     * 方法1 递归
     */
    public static int longestCommonSubsequence1(String text1, String text2) {
        if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
            return 0;
        }
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        return process(str1, str2, str1.length - 1, str2.length - 1);
    }

    public static int process(char[] str1, char[] str2, int i, int j) {
        if (i == 0 && j == 0) {
            return str1[0] == str2[0] ? 1 : 0;
        } else if (i == 0) {
            if (str1[0] == str2[j]) {
                return 1;
            } else {
                return process(str1, str2, i, j - 1);
            }
        } else if (j == 0) {
            if (str1[i] == str2[0]) {
                return 1;
            } else {
                return process(str1, str2, i - 1, j);
            }
        } else {
            int p1 = process(str1, str2, i - 1, j);
            int p2 = process(str1, str2, i, j - 1);
            int p3 = process(str1, str2, i - 1, j - 1);
            if (str1[i] == str2[j]) {
                p3++;
            }
            return Math.max(p1, Math.max(p2, p3));
        }
    }

    /**
     * 方法2 dp
     */
    public static int longestCommonSubsequence2(String text1, String text2) {
        if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) {
            return 0;
        }
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int j = 1; j < str2.length; j++) {
            if (str1[0] == str2[j]) {
                dp[0][j] = 1;
            } else {
                dp[0][j] = dp[0][j - 1];
            }
        }
        for (int i = 1; i < str1.length; i++) {
            if (str1[i] == str2[0]) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                int p1 = dp[i - 1][j];
                int p2 = dp[i][j - 1];
                int p3 = dp[i - 1][j - 1];
                if (str1[i] == str2[j]) {
                    p3++;
                }
                dp[i][j] = Math.max(p1, Math.max(p2, p3));
            }
        }
        return dp[str1.length - 1][str2.length - 1];
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubsequence2("abcde", "ace"));    // 3
        System.out.println(longestCommonSubsequence2("abc", "abc"));      // 3
        System.out.println(longestCommonSubsequence2("abc", "def"));      // 0
    }

}
